package com.note.feng.leetcode.algorithms.easy.tree;

import com.note.feng.dataStructureAlgorithm.queue.ArrayQueue;
import com.note.feng.dataStructureAlgorithm.queue.Queue;

public class HundredOne {

    /**
     * 101. 对称二叉树
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     *
     * 示例 1：
     *
     * 输入：root = [1,2,2,3,4,4,3]
     * 输出：true
     * 示例 2：
     *
     * 输入：root = [1,2,2,null,3,null,3]
     * 输出：false
     *  
     * 提示：
     *
     * 树中节点数目在范围 [1, 1000] 内
     * -100 <= Node.val <= 100
     *  
     * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/symmetric-tree
     */
    /**
     *解法：
     * 递归遍历
     * 1、如果左右子树都为空，返回true
     * 2、如果左右子树有一个为空，返回false
     * 3、如果左右子树都不为空，val值不相等，返回false
     * 左边的左子树，与右边的右子树对比；
     * 左边的右子树，与右边的左子树对比；
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return leftRightIsSymmetric(root.left, root.right);
    }

    private boolean leftRightIsSymmetric(TreeNode lNode, TreeNode rNode){
        if(lNode == null && rNode == null){
            return true;
        }
        if(lNode == null || rNode == null){
            return false;
        }
        if(lNode.val != rNode.val){
            return false;
        }
        return leftRightIsSymmetric(lNode.left, rNode.right) && leftRightIsSymmetric(lNode.right, rNode.left);
    }

    /**
     * 解法二：
     * 非递归遍历：
     * 借助队列，实现，每次加入队列2个节点，取出2个节点，对比该节点是否符合对称要求
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root) {
        Queue<TreeNode> queue = new ArrayQueue<>();
        queue.enqueue(root);
        queue.enqueue(root);
        while(!queue.isEmpty()){
            TreeNode l = queue.dequeue();
            TreeNode r = queue.dequeue();
            if(l == null && r == null){
                continue;
            }
            if(l == null || r == null || l.val != r.val){
                return false;
            }
            queue.enqueue(l.left);
            queue.enqueue(r.right);
            queue.enqueue(l.right);
            queue.enqueue(r.left);
        }
        return true;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
